#include <stdio.h>

/*待排序的数组元素的编号从0开始到num_elements-1。
要求：
1.	实现如下声明的insertion_sort函数。
2.	在把从1到num_elements-1位置上的每个元素放置到合适位置上之后，
 将此时unsorted_array里的全部元素的值打印到标准输出，
 元素值之间仅用英文的空格分隔，每次输出 之后换行。
 比如输入的unsorted_array数组里依次包含4个元素4, 3, 2, 1。那么输出的内容应该如下：
3 4 2 1
2 3 4 1
1 2 3 4

*/
void insertion_sort(int unsorted_array[], int num_elements){
    int temp,i,j;
    for(i = 1;i< num_elements;i++){
        temp = unsorted_array[i];
        for(j = i-1;j >= 0 && unsorted_array[j]>temp;j--){
            unsorted_array[j+1]=unsorted_array[j];
        }
        unsorted_array[j+1] = temp;
        for(int k = 0;k <num_elements;k++){
            printf("%d ",unsorted_array[k]);
        }
        printf("\n");
    }
}

/*待排序的数组元素的编号从0开始到total_num_elements-1。
要求：
1.	实现如下声明的partition函数；永远选择low位置上的元素作为pivot支撑元素；在partition函数返回pivot支撑元素的位置之前，把unsorted_array里的所有元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出 之后换行。
2.	递归实现如下声明的quick_sort函数；在每次递归时先处理左侧的子数组，再处理右侧的子数组；quick_sort必须调用partition函数获取pivot支撑元素的位置。
3.	比如当输入的unsorted_array数组的元素依次为 3, 1, 2, 5, 4时，输出应该为：
2 1 3 5 4
1 2 3 5 4
1 2 3 4 5
*/

int partition(int L[], int low,  int  high, int total_num_elements){
    int pivot =L[low];
    int temp;
    while (low<high){
        while (low < high&& L[high] >= pivot){
            high--;
        }
        temp = L[low];
        L[low] = L[high];
        L[high] = temp;
        while (low <high && L[low] <= pivot ){
            low++;
        }
        temp = L[low];
        L[low] = L[high];
        L[high] = temp;
    }
    pivot = low;
    for(int k = 0;k <total_num_elements;k++){
        printf("%d ",L[k]);
    }
    printf("\n");
    return pivot;
};
void QSort(int L[], int low,  int  high, int total_num_elements){
    int pivot;
    if (low<high){
        pivot = partition(L,low,high,total_num_elements);
        QSort(L,low,pivot-1,total_num_elements);
        QSort(L,pivot+1,high,total_num_elements);
    }
}
/*
待排序的数组元素的编号从0开始到num_elements-1
要求：
1.	实现如下声明的heap_sort函数。
2.	在每次对已经建好的最大堆进行调整然后把当前根里的最大值放置到合适正确的位置之后、再次调整形成最大堆之前，把unsorted_array里的所有元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出之后换行。例如：
10 60 12 40 30 8 70
8 40 12 10 30 60 70
8 30 12 10 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
*/
void a_heap(int  A[],int target,int n){
    int i = target;
    int j = 2 *i +1;
    int temp = A[i];
    while (j <= n)
    {
        if(j < n && A[j] < A[j + 1])
        {
            j++;
        }
        if(temp < A[j])
        {
            A[i] = A[j];
            i = j;
            j = 2*j + 1;
        } else{
            break;
        }
    }
    A[i] = temp;
}
void heap_sort(int unsorted_array[], int num_elements){
    int i;
    for(i = num_elements/2 - 1; i >= 0;i--){
        a_heap(unsorted_array,i,num_elements-1);
    }
    int temp;
    for(i = num_elements - 1;i > 0;i--){
        temp = unsorted_array[0];
        unsorted_array[0] = unsorted_array[i];
        unsorted_array[i] = temp;
        a_heap(unsorted_array,0,i-1);
        for(int i = 0;i<7;i++){
            printf("%d ",unsorted_array[i]);
        }
        printf("\n");

    }
}

void main(){
    int unsorted_array[] = {4,3,2,1};
    printf("插入排序：\n");
    insertion_sort(unsorted_array,4);
    int L[] = {3,1,2,5,4};
    printf("快速排序：\n");
    QSort(L,0,4,5);
    int unsorted_array1[] = {10,60,12,40,30,8,70};
    printf("堆排序：\n");
    heap_sort(unsorted_array1,7);
}